#include <bits/stdc++.h>
using namespace std;

#define S64_t long long
#define U64_t unsigned long long
 
 
#define MAXN 100
#define MAXV 1000
int f[MAXN], w[MAXN], c[MAXN];

int f2[MAXN][MAXV];
int bag01_v1(int n, int v){
   for(int i=1; i<=n; i++)
      for(int j=0; j<=v; j++)
         if(j - w[i] >= 0) f2[i][j] = max(f2[i - 1][j], f2[i - 1][j - w[i]] + c[i]);
         else f2[i][j] = f2[i - 1][j];
   return f2[n][v];
}

void clear()
{
   memset(f, 0, sizeof(f));
   memset(f2, 0, sizeof(f));
}

int bag01_v2(int n, int v, int *w, int *c, int *f){
   clear();
   for(int i=1; i<=n; i++)
      for(int j=v; j>=0; j--)
         if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + c[i]);
   return f[v];
}

int bag01_v3(int n, int v, int *w, int *c, int *f){
   clear();
   for(int i=1; i<=n; i++)
      for(int j=v; j>=w[i]; j--) f[j] = max(f[j], f[j - w[i]] + c[i]);
   return f[v];
}

int main()
{
   int m, n;
   scanf("%d%d", &m, &n);
   for(int i=1; i<=n; i++) scanf("%d%d", &w[i],&c[i]);
   printf("%d\n",  bag01_v1(n, m));
   printf("%d\n",  bag01_v2(n, m, w, c, f));
   printf("%d\n",  bag01_v3(n, m, w, c, f));
   return 0;
}